package com.shm.leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: shm
 * @dateTime: 2020/10/26 21:18
 * @description: 1365. 有多少小于当前数字的数字
 * 给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
 *
 * 换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
 *
 * 以数组形式返回答案。
 *
 * 示例 1：
 *
 * 输入：nums = [8,1,2,2,3]
 * 输出：[4,0,1,1,3]
 * 解释：
 * 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
 * 对于 nums[1]=1 不存在比它小的数字。
 * 对于 nums[2]=2 存在一个比它小的数字：（1）。
 * 对于 nums[3]=2 存在一个比它小的数字：（1）。
 * 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。
 * 示例 2：
 *
 * 输入：nums = [6,5,4,8]
 * 输出：[2,1,0,3]
 * 示例 3：
 *
 * 输入：nums = [7,7,7,7]
 * 输出：[0,0,0,0]
 *
 *
 * 提示：
 *
 * 2 <= nums.length <= 500
 * 0 <= nums[i] <= 100
 */
public class SmallerNumbersThanCurrent {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for(int i =0;i<n;i++){
            int cnt=0;
            for(int j=0;j<n;j++){
                if(j!=i&&nums[j]<nums[i]){
                    cnt++;
                }
            }
            ans[i]=cnt;
        }
        return ans;
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/26 21:32
     * @description: 方法三：计数排序
     * 注意到数组元素的值域为 [0,100][0,100]，所以可以考虑建立一个频次数组 cntcnt ，cnt[i]cnt[i] 表示数字 ii 出现的次数。那么对于数字 ii 而言，小于它的数目就为 cnt[0...i-1]cnt[0...i−1] 的总和。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N + K)O(N+K)，其中 KK 为值域大小。需要遍历两次原数组，同时遍历一次频次数组 cntcnt 找出前缀和。
     *
     * 空间复杂度：O(K)O(K)。因为要额外开辟一个值域大小的数组。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/solution/you-duo-shao-xiao-yu-dang-qian-shu-zi-de-shu-zi--2/
     */
    public int[] smallerNumbersThanCurrent_2(int[] nums) {
        int[] cnt = new int[101];
        for (int num : nums) {
            cnt[num]++;
        }
        for (int i = 1; i < cnt.length; i++) {
            cnt[i]+=cnt[i-1];
        }
        int[] ans = new int[nums.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i]=nums[i]==0?0:cnt[nums[i]-1];
        }
        return ans;
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/26 21:50
     * @description: 方法二：快速排序
     * 我们也可以将数组排序，并记录每一个数在原数组中的位置。对于排序后的数组中的每一个数，我们找出其左侧第一个小于它的数，这样就能够知道数组中小于该数的数量。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N\log N)O(NlogN)，其中 NN 为数组的长度。排序需要 O(N\log N)O(NlogN) 的时间，随后需要 O(N)O(N) 时间来遍历。
     *
     * 空间复杂度：O(N)O(N)。因为要额外开辟一个数组。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/solution/you-duo-shao-xiao-yu-dang-qian-shu-zi-de-shu-zi--2/
     */
    public int[] smallerNumbersThanCurrent_3(int[] nums) {
        int n = nums.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        int[] ans = new int[n];
        int pre = -1;
        for (int i = 0; i < n; i++) {
            if (pre==-1||arr[i][0]!=arr[i-1][0]){
                pre=i;
            }
            ans[arr[i][1]]=pre;
        }
        return ans;
    }
}
